package tianhao.luo.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 哈夫曼树
 * @author: tianhao.luo@hand-china.com 2021/6/25  下午4:02
 */
public class HuffmanTree {

    private int[] array;

    public HuffmanTree(int[] array) {
        this.array = array;
    }

    public void preOrder(Node root){
        if (root !=null){
            root.preOrder();
        }else {
            System.out.println("空树");
        }
    }

    /**
     * 创建哈夫曼树
     */
    public Node createHuffmanTree(){
        List<Node> nodes = new ArrayList<>();
        // 1.利用数组元素构建Node
        for (int i : array) {
            Node node = new Node(i);
            nodes.add(node);
        }

        // 处理的过程是一个循环
        while (nodes.size()> 1){
            // 2.将构建好的node放入到arrayList中,从小到大排序(和实现的Comparable有关)
            Collections.sort(nodes);

            System.out.println("nodes:"+nodes);

            // 取出根节点权值最小的两颗二叉树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            // 构建一颗新的二叉树
            Node parentNode = new Node(leftNode.value+rightNode.value);
            parentNode.left = leftNode;
            parentNode.right = rightNode;

            // 从arrayList中删除处理过的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            // 将parent加入nodes中
            nodes.add(parentNode);

            System.out.println("第一次处理后:"+nodes);
        }
        return nodes.get(0);
    }
}
